package main

func main() {

}

/**
丑数是只包含质因数 2、3、 5 的正整数；1 是丑数
*/

/*
*
1 是丑数，那么1*2  1*3  1*5得到数都是丑数，有2,3,5
最小的是2，那么第2个丑数2

接着2*2 2*3 2*5得到的数都是丑数，有4,6,10
好，现在丑数有3 4 5 6 10
最小的是3，那么第3个丑数是3

接着，3*2 3*3 3*5得到的数都是丑数，有6,9,15
好，现在丑数有4,5,6,9,15
最小的数是4，那么第4个丑数是4
....
*/
func nthUglyNumber(n int) int {
	// dp[i] 第 i个丑数是多少
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1

	// 从第二个丑数开始算
	// 初始三个指针都指向1
	for i, cur1, cur2, cur3, a, b, c := 2, 1, 1, 1, 0, 0, 0; i < n+1; i++ {
		a = dp[cur1] * 2
		b = dp[cur2] * 3
		c = dp[cur3] * 5
		// 算出来的最小的丑数
		uglyN := min(a, min(b, c))
		dp[i] = uglyN

		// 由哪个指针算出来的，哪个指针就往后移动一个
		if a == uglyN {
			cur1++
		}
		if b == uglyN {
			cur2++
		}
		if c == uglyN {
			cur3++
		}
	}
	return dp[n]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
